CF896C Willem, Chtholly and Seniorious < ODT >

Problem

Willem, Chtholly and Seniorious

Description

— Willem…
— What’s the matter?
— It seems that there’s something wrong with Seniorious…
— I’ll have a look…

is made by linking special talismans in particular order.
After over years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.
has pieces of talisman. Willem puts them in a line, the of which is an integer .
In order to maintain it, Willem needs to perform operations.
There are four types of operations:

1. : For each such that , assign to .
2. : For each such that , assign to .
3. : Print the smallest number in the index range , i.e. the element at the position if all the elements such that are taken and sorted into an array of non-decreasing integers. It’s guaranteed that .
4. : Print the sum of the power of such that , modulo , i.e. .

Input

The only line contains four integers (,,.
The initial values and operations are generated using following pseudo code:

def rnd():
    ret = seed
    seed = (seed * 7 + 13) mod 1000000007
    return ret

for i = 1 to n:
    a[i] = (rnd() mod vmax) + 1

for i = 1 to m:
    op = (rnd() mod 4) + 1
    l = (rnd() mod n) + 1
    r = (rnd() mod n) + 1
    if (l > r): 
         swap(l, r)
    if (op == 3):
        x = (rnd() mod (r - l + 1)) + 1
    else:
        x = (rnd() mod vmax) + 1
    if (op == 4):
        y = (rnd() mod vmax) + 1

Here is the type of the operation mentioned in the legend.

Output

For each operation of types or , output a line containing the answer.

Example

Input 1

10 10 7 9

Output 1

2
1
0
3

Input 2

10 10 9 9

Output 2

1
1
3
3

Note

In the first example, the initial array is .
The operations are:

标签：ODT

Translation

给出一个长为级别的初始数组，要求维护四种操作：

1. 将中的每个数
2. 将中的每个数赋为
3. 询问区间中的第小值
4. 询问

Solution

裸题。

用一棵set维护若干区间，每个区间都是值相等的一段。
对于操作，将与有交集的所有区间都拿出来，如果是包含的区间，可以直接将区间值；如果是部分相交，则把区间拆成两部分（或三部分），分别赋值后删除原区间，插入新区间。
对于操作，将所有包含区间提出并删除，分成至多三段，即，其中和是与部分相交的两个区间的左端点和右端点。将左右两个区间赋值为原来的值，将中间的区间赋值为。
对于询问，将所有相交区间合起来排序再枚举判断即可。
对于询问，将所有相交区间提出来得到每个值的个数，直接统计贡献即可。

复杂度证明见lxl的题解

Code

#include <bits/stdc++.h>
#define fir first
#define sec second
#define MAX_N 100000
#define MOD 1000000007
using namespace std;
typedef long long lnt;
typedef pair<int,int> pii;
typedef pair<lnt,int> pli;
typedef map<pii,lnt>::iterator IT;
map <pii, lnt> s;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, seed, vmx, a[MAX_N+5];
int rnd() {int ret = seed; return seed = (int)((7LL*seed+13)%MOD), ret;}
void qry(int &op, int &l, int &r, int &x, int &y) {
    op = rnd()%4+1, l = rnd()%n+1, r = rnd()%n+1; if (l > r) swap(l, r);
    x = rnd()%(op == 3 ? (r-l+1) : vmx)+1; y = op == 4 ? rnd()%vmx+1 : 0;
}
lnt pw(lnt x, lnt k, lnt p) {
    lnt ret = 1LL; x %= p;
    for (; k; k>>=1, (x *= x) %= p)
        if (k&1) (ret *= x) %= p;
    return ret;
}
int main() {
    read(n), read(m), read(seed), read(vmx);
    for (int i = 1; i <= n; i++) a[i] = rnd()%vmx+1;
    for (int i = 1; i <= n; i++) s[pii(i, i)] = a[i];
    for (int i = 1, op, l, r, x, y; i <= m; i++) {
        qry(op, l, r, x, y); IT it = s.lower_bound(pii(l, l));
        if (op == 1) {
            if (it->fir.fir != l) {
                it--;
                pii pr = pii(it->fir.fir, l-1), cur = pii(l, min(r, it->fir.sec));
                if (it->fir.sec <= r) s[pr] = it->sec, s[cur] = it->sec+x;
                else s[pr] = it->sec, s[cur] = it->sec+x, s[pii(r+1, it->fir.sec)] = it->sec;
                s.erase(it), it = s.lower_bound(pii(l+1, l+1));
            }
            for (; it != s.end() && it->fir.fir <= r; it++)
                if (it->fir.sec <= r) it->sec += x;
                else {
                    s[pii(it->fir.fir, r)] = it->sec+x, 
                    s[pii(r+1, it->fir.sec)] = it->sec, 
                    s.erase(it); break;
                }
        }
        if (op == 2) {
            if (it->fir.fir != l) {
                it--; pii pr = pii(it->fir.fir, l-1);
                if (it->fir.sec > r) s[pii(r+1, it->fir.sec)] = it->sec;
                s[pr] = it->sec, s.erase(it), it = s.lower_bound(pii(l+1, l+1));
            }
            for (; it != s.end() && it->fir.fir <= r; s.erase(it), it = s.lower_bound(pii(l, l)))
                if (it->fir.sec > r) s[pii(r+1, it->fir.sec)] = it->sec;
            s[pii(l, r)] = x;
        }
        if (op == 3) {
            vector <pli> vec;
            if (it->fir.fir != l)
                it--, vec.push_back(pli(it->sec, min(r, it->fir.sec)-l+1)), it++;
            for (; it != s.end() && it->fir.fir <= r; it++)
                vec.push_back(pli(it->sec, min(r, it->fir.sec)-it->fir.fir+1));
            sort(vec.begin(), vec.end());
            for (int j = 0; j < (int)vec.size(); x -= vec[j++].sec)
                if (x <= vec[j].sec) {printf("%lld\n", vec[j].fir); break;}
        }
        if (op == 4) {
            lnt ans = 0;
            if (it->fir.fir != l)
                it--, (ans += pw(it->sec, x, y)*(min(r, it->fir.sec)-l+1)%y) %= y, it++;
            for (; it != s.end() && it->fir.fir <= r; it++)
                (ans += pw(it->sec, x, y)*(min(r, it->fir.sec)-it->fir.fir+1)%y) %= y;
            printf("%lld\n", ans);
        }
    }
    return 0;
}